﻿#region << 版 本 注 释 >>
/*----------------------------------------------------------------
 * 版权所有 (c) 2022 北京超维景生物科技有限公司 保留所有权利。
 * 
 * 创建者：huangyang
 * 电子邮箱：huangyang@tvscope.cn
 * 创建时间：2023/3/2 9:54:39
 * 版本：V1.0.0
 * 描述：
 *
 * ----------------------------------------------------------------
 * 修改人：
 * 时间：
 * 修改说明：
 *
 * 版本：V1.0.1
 *----------------------------------------------------------------*/
#endregion << 版 本 注 释 >>

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ImageK.Process
{
    /// <summary>
    /// Used by the Roi classes to return float coordinate arrays and to
    /// determine if a point is inside or outside of spline fitted selections.
    /// </summary>
    public class FloatPolygon
    {
        private Rectangle bounds = Rectangle.Empty;
        private float minX, minY, maxX, maxY;


		/** The number of points. */
		public int npoints;

		/* The array of x coordinates. */
		public float[] xpoints;

		/* The array of y coordinates. */
		public float[] ypoints;

		/** Constructs an empty FloatPolygon. */
		public FloatPolygon()
		{
            npoints = 0;
            xpoints = new float[10];
            ypoints = new float[10];
		}

		/** Constructs a FloatPolygon from x and y arrays. */
		public FloatPolygon(float[] xpoints, float[] ypoints)
		{
			if (xpoints.Length != ypoints.Length)
				throw new ArgumentException("xpoints.length!=ypoints.length");
			this.npoints = xpoints.Length;
			this.xpoints = xpoints;
			this.ypoints = ypoints;
		}

		/** Constructs a FloatPolygon from x and y arrays. */
		public FloatPolygon(float[] xpoints, float[] ypoints, int npoints)
		{
			this.npoints = npoints;
			this.xpoints = xpoints;
			this.ypoints = ypoints;
		}

		/** Returns 'true' if the point (x,y) is inside this polygon. This is a Java
		 *  version of the remarkably small C program by W. Randolph Franklin at
		 *  http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html#The%20C%20Code
		 * 
		 *  In the absence of numerical errors, x coordinates exactly at a boundary are taken as if
		 *  in the area immediately at the left of the boundary. For horizontal boundaries,
		 *  y coordinates exactly at the border are taken as if in the area immediately above it
		 *  (i.e., in decreasing y direction).
		 *  The ImageJ convention of an offset of 0.5 pixels between pixel centers and outline
		 *  coordinates is not taken into consideration; this method returns the purely
		 *  geometrical relationship.
		 */
		public bool contains(double x, double y)
		{
			bool inside = false;
			for (int i = 0, j = npoints - 1; i < npoints; j = i++)
			{
				if (((ypoints[i] >= y) != (ypoints[j] >= y)) &&
						(x > ((double)xpoints[j] - xpoints[i]) * ((double)y - ypoints[i]) / ((double)ypoints[j] - ypoints[i]) + (double)xpoints[i]))
					inside = !inside;
			}
			return inside;
		}

		/** A version of contains() that accepts float arguments. */
		public bool contains(float x, float y)
		{
			return contains((double)x, (double)y);
		}

		public Rectangle getBounds()
		{
			if (npoints == 0)
				return new Rectangle();
			if (bounds == Rectangle.Empty)
				calculateBounds(xpoints, ypoints, npoints);
			return bounds;
		}

		public RectangleF getFloatBounds()
		{
			if (npoints == 0)
				return new RectangleF();
			if (bounds == Rectangle.Empty)
				calculateBounds(xpoints, ypoints, npoints);
			return new RectangleF(minX, minY, maxX - minX, maxY - minY);
		}

		void calculateBounds(float[] xpoints, float[] ypoints, int npoints)
		{
			minX = float.MaxValue;
			minY = float.MaxValue;
			maxX = float.MinValue;
			maxY = float.MinValue;
			for (int i = 0; i < npoints; i++)
			{
				float x = xpoints[i];
				minX = Math.Min(minX, x);
				maxX = Math.Max(maxX, x);
				float y = ypoints[i];
				minY = Math.Min(minY, y);
				maxY = Math.Max(maxY, y);
			}
			int iMinX = (int)Math.Floor(minX);
			int iMinY = (int)Math.Floor(minY);
			bounds = new Rectangle(iMinX, iMinY, (int)(maxX - iMinX + 0.5), (int)(maxY - iMinY + 0.5));
		}

		public void addPoint(float x, float y)
		{
			if (npoints == xpoints.Length)
			{
				float[] tmp = new float[npoints * 2];
                Array.Copy(xpoints, 0, tmp, 0, npoints);
				xpoints = tmp;
				tmp = new float[npoints * 2];
                Array.Copy(ypoints, 0, tmp, 0, npoints);
				ypoints = tmp;
			}
			xpoints[npoints] = x;
			ypoints[npoints] = y;
			npoints++;
			bounds = Rectangle.Empty;
		}

		public void addPoint(double x, double y)
		{
			addPoint((float)x, (float)y);
		}

		public FloatPolygon duplicate()
		{
			int n = this.npoints;
			float[] xpoints = new float[n];
			float[] ypoints = new float[n];
			Array.Copy(this.xpoints, 0, xpoints, 0, n);
			Array.Copy(this.ypoints, 0, ypoints, 0, n);
			return new FloatPolygon(xpoints, ypoints, n);
		}

		/* Returns the length of this polygon or line. */
		public double getLength(bool isLine)
		{
			double dx, dy;
			double length = 0.0;
			for (int i = 0; i < (npoints - 1); i++)
			{
				dx = xpoints[i + 1] - xpoints[i];
				dy = ypoints[i + 1] - ypoints[i];
				length += Math.Sqrt(dx * dx + dy * dy);
			}
			if (!isLine)
			{
				dx = xpoints[0] - xpoints[npoints - 1];
				dy = ypoints[0] - ypoints[npoints - 1];
				length += Math.Sqrt(dx * dx + dy * dy);
			}
			return length;
		}

		/** Uses the gift wrap algorithm to find the convex hull of all points in
		 *  this FloatPolygon and returns it as a new FloatPolygon.
		 *  The sequence of the points on the convex hull is counterclockwise. */
		public FloatPolygon getConvexHull()
		{
			float[] xx = new float[npoints];
			float[] yy = new float[npoints];
			int n2 = 0;
			float smallestY = float.MaxValue;
			for (int i = 0; i < npoints; i++)
			{
				float y = ypoints[i];
				if (y < smallestY)
					smallestY = y;
			}
			float smallestX = float.MaxValue;
			int p1 = 0;               // find the starting point: among all points with the smallest y, the one with the smallest x
			for (int i = 0; i < npoints; i++)
			{
				float x = xpoints[i];
				float y = ypoints[i];
				if (y == smallestY && x < smallestX)
				{
					smallestX = x;
					p1 = i;
				}
			}
			int pstart = p1;          // the start point is always on the convex hull
			int count = 0;
			do
			{
				double x1 = xpoints[p1];
				double y1 = ypoints[p1];
				int p2 = p1;
				double x2 = 0, y2 = 0;
				do
				{
					p2++; if (p2 == npoints) p2 = 0;
					if (p2 == p1) break;           // all points have the same coordinates as p1
					x2 = xpoints[p2];              // p2 is a candidate for the convex hull
					y2 = ypoints[p2];
				} while (x2 == x1 && y2 == y1);    // make sure p2 is not identical to p1

				int p3 = p2 + 1; if (p3 == npoints) p3 = 0;
				if (p2 != p1) do
					{
						double x3 = xpoints[p3];
						double y3 = ypoints[p3];
						//The following is the cross product r12 x r23 = (x2-x1)*(y3-y2) - (y2-y1)*(x3-x2),
						//where r12 and r23 are the vectors from p1 to p2 and p2 to p3, respectively.
						//It is positive if the path from p1 via p2 to p3 bends clockwise at p2
						double determinate = x1 * (y2 - y3) - y1 * (x2 - x3) + (y3 * x2 - y2 * x3);
						bool collinearAndFurther = false;
						if (determinate == 0 && p3 != p2)
						{ //avoid collinear points on the hull: take longest possible side length
							double d2sqr = sqr(x2 - x1) + sqr(y2 - y1);
							double d3sqr = sqr(x3 - x1) + sqr(y3 - y1);
							collinearAndFurther = d3sqr > d2sqr;
						}
						if (determinate > 0 || collinearAndFurther)
						{
							x2 = x3; y2 = y3; p2 = p3;       // p2 is not on the convex hull, p3 becomes the new candidate
						}
						p3++; if (p3 == npoints) p3 = 0;
					} while (p3 != p1);                // all points have been checked whether they are the next one on the convex hull

				xx[n2] = (float)x1;                // save p1 as a point on the convex hull
				yy[n2] = (float)y1;
				n2++;

				if (p2 == p1) break;               // happens only if there was only one unique point
				p1 = p2;
				if (n2 > 1 && xpoints[p1] == xx[0] && ypoints[p1] == yy[0]) break; //all done but pstart was missed because of duplicate points
			} while (p1 != pstart);
			return new FloatPolygon(xx, yy, n2);
		}

		public void translate(double x, double y)
		{
			float fx = (float)x;
			float fy = (float)y;
			for (int i = 0; i < npoints; i++)
			{
				xpoints[i] += fx;
				ypoints[i] += fy;
			}
		}

		private double sqr(double x) { return x * x; }

		private double crossProduct(double x1, double y1, double x2, double y2)
		{
			return (double)x1 * y2 - (double)x2 * y1;
		}

		public String toString()
		{
			return "FloatPolygon[npoints=" + npoints + "]";
		}
	}
}
